<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<meta name="viewport" content="width=device-width,initial-scale=1,minimum-scale=1,maximum-scale=1,user-scalable=no" />
		<link rel="stylesheet" type="text/css" href="./css/bootstrap.min.css" />
		<script src="./js/jquery.min.js" type="text/javascript" charset="utf-8"></script>
		<title>最长公共子序列-邓永盛</title>
		<style type="text/css">
			.form-control {
				display: inline-block;
				max-width: 170px;
			}

			#speed_sel {
				width: 170px;
				display: inline-block;
			}

			table {
				margin-top: 10px;
			}

			#table_area table td {
				border-top-style: none;
				border-width: 2px;
				border-style: solid;
				border-color: #ffffff;
				border-radius: 10px;
				background-color: #e7e7e7;
			}

			table td:hover {
				box-shadow: 0px 0px 3px 3px #ffffff inset;
			}

			#table_area .stress {
				color: #ffffff;
				font-weight: bold;
				background-color: #999999;
			}

			#table_area .match {
				color: white;
				background-color: #5cb85c;
			}

			#table_area .miss {
				color: white;
				background-color: #f0ad4e;
			}

			#table_area .current {
				color: white;
				background-color: #f54d4d;
			}

			.result {
				display: none;
				padding-bottom: 30px;
				font-weight: bold;
			}
		</style>
	</head>
	<body>
		<div class="container">
			<h1 class="page-header text-center">最长公共子序列</h1>
			<div class="text-center">
				<div class="form-group">
					<label for="main_str">主串：</label>
					<input type="text" class="form-control" id="main_str" value="algorithms" />
				</div>
				<div class="form-group">
					<label for="sub_str">子串：</label>
					<input type="text" class="form-control" id="sub_str" value="alchemist" />
				</div>
				<div class="form-group">
					<label for="speed_sel">速度(<span id="speed_show">500</span>)：</label>
					<input type="range" id="speed_sel" min="10" max="2000" value="80">
					<script type="text/javascript">
						var speed = parseInt($('#speed_sel').val());
						$('#speed_show').text($('#speed_sel').val());
						$('#speed_sel').on('change', function() {
							$('#speed_show').text($('#speed_sel').val());
							speed = parseInt($('#speed_sel').val());
						});
					</script>
				</div>
				<button type="button" class="btn btn-success" id='enter'>确定</button>
			</div>
			<div class="container text-center" id="table_area">
				<table class="table"> </table>
				<button class="btn btn-success center-block" id='btn_pause' style="display: none;">暂停</button>
				<script type="text/javascript">
					var pause = false;
					$('#btn_pause').on('click', function() {
						if (pause)
							$('#btn_pause').text('暂停');
						else
							$('#btn_pause').text('继续');
						pause = !pause;
					});
				</script>
			</div>
			<div class="container text-center result">
				<h4>最长公共子序列为：</h4>
			</div>
		</div>
		<script type="text/javascript">
			var semaphore = -1;
			var mainstr, substr;
			var i, j, interval;
			var table;
			// 记录所有的特殊点
			var special_points = new Array();
			$('#enter').on('click', function() {
				special_points = new Array();
				$('#enter').text('重新开始');
				// 清空内部元素
				$('#table_area table').remove();
				$('#table_area label').remove();
				// 
				$('.result').hide();
				// 获取主串
				mainstr = $('#main_str').val();
				// 获取子串
				substr = $('#sub_str').val();
				// 定位到表格
				$('#table_area').prepend(`<table class="table"> </table>`);
				table = $('#table_area table');
				// 按照字串的长度生成行
				for (let i = 0; i < substr.length + 1; i++) {
					// 生成行
					row = $('<tr> </tr>');
					for (let j = 0; j < mainstr.length + 1; j++) {
						// 生成单元格
						row.append('<td>&nbsp;&nbsp;</td>')
					}
					table.append(row);
				}
				tbody = table.children('tbody');
				// 填充表格的第一行
				for (let i = 0; i < mainstr.length; i++) {
					cell = getCell(0, 1 + i);
					cell.addClass('stress');
					cell.text(mainstr[i]);
				}
				// 填充第一列
				for (let i = 0; i < substr.length; i++) {
					cell = getCell(i + 1, 0);
					cell.addClass('stress');
					cell.text(substr[i]);
				}
				// 最左上角单元格设置无背景颜色
				getCell(0, 0).css('background-color', 'unset');
				// 重新排版底部版权信息
				setPosition();
				// 显示暂停按钮
				$('#btn_pause').css('display', 'block');
				// 初始化循环变量
				i = 0, j = 0;
				semaphore++;
				loop();
			});
			// 定位一个单元格
			function getCell(row, col) {
				return $('#table_area table tbody').children('tr:nth-child(' + (row + 1) + ')').children('td:nth-child(' + (col + 1) +
					')');
			}
			// 获取单元格中的数值
			function getCellVal(row, col) {
				if (row == 0 || col == 0) {
					// 越界直接返回 0
					return 0;
				} else {
					return parseInt(getCell(row, col).text());
				}
			}

			function loop() {
				// 如果启动了多次，就结束此次循环，且不启动新的循环
				if (semaphore) {
					semaphore--;
					return;
				}
				// 暂停
				if (pause) {
					setTimeout(loop, speed);
					return;
				}
				$('td.current').removeClass('current');
				// 循环条件
				if (j < mainstr.length && i < substr.length) {
					current_cell = getCell(i + 1, j + 1);
					current_cell.addClass('current');
					if (mainstr[j] === substr[i]) {
						let val = getCellVal(i, j) + 1;
						current_cell.text(val);
						current_cell.addClass('match');
						special_points.push([i, j, substr[i], val]);
					} else {
						current_cell.text(Math.max(getCellVal(i + 1, j), getCellVal(i, j + 1)));
						current_cell.addClass('miss');
					}
					if (j + 1 == mainstr.length) {
						i++;
						j = 0;
					} else {
						j++;
					}
					setTimeout(loop, speed);
				} else {
					// 结束循环
					// 信号量归零，防止无法重新启动
					semaphore--;
					// 隐藏暂停按钮
					$('#btn_pause').css('display', 'none');
					// 确定
					$('#enter').text('确定');
					// 构造LCS
					lcs = constructLCS();
					if (lcs.length == 0) {
						$('.result h4').text('没有公共子序列');
						$('.result h4').css('color', 'red');
					} else {
						$('.result h4').text('最长公共子序列为：' + lcs);
						$('.result h4').css('color', 'unset');
					}
					$('.result').show();
					// 重新调整页面底部栏位置
					setPosition();
				}

			}
			// 构造最长公共子序列
			function constructLCS(x, y) {
				var lcs = new Array();
				console.log(special_points);
				if (special_points.length == 0) {
					console.log("没有公共子序列");
					return '';
				}
				// 找到值最大的一个点作为起始点
				// maxval = 0;
				maxValIndex = 0;
				special_points.forEach(function(item, index) {
					if (item[3] > special_points[maxValIndex][3]) {
						maxValIndex = index;
					}
				});
				// 取出并删除最大的那个元素
				item = special_points[maxValIndex];
				special_points.splice(maxValIndex, 1);
				lcs.push(item[2]);
				// 给这个单元格上色
				cell = getCell(item[0] + 1, item[1] + 1);
				cell.css('box-shadow', 'inset 0px 0px 5px 8px #00fd65');
				cell.css('font-weight', 'bold');
				cell.css('font-size', 'large');
				while (special_points.length > 0) {
					// 删除在当前点右侧和下方的所有点
					for (let i = 0; i < special_points.length; i++) {
						x = special_points[i];
						if (x[0] >= item[0] || x[1] >= item[1]) {
							special_points.splice(i, 1);
							i--;
						}
					}
					var nearest_p = 0;
					// 找到离当前点最近的一点
					special_points.forEach(function(x, index) {
						if ((Math.pow(item[0] - special_points[nearest_p][0], 2) + Math.pow(item[1] - special_points[nearest_p][1], 2)) >
							(Math.pow(
								x[0] - special_points[nearest_p][0], 2) + Math.pow(x[1] - special_points[nearest_p][1], 2))) {
							nearest_p = index;
						}
					});
					item = special_points[nearest_p];
					if (item != undefined) {
						lcs.push(item[2]);
						cell = getCell(item[0] + 1, item[1] + 1);
						cell.css('box-shadow', 'inset 0px 0px 5px 8px #00fd65');
						cell.css('font-weight', 'bold');
						cell.css('font-size', 'large');
						special_points.splice(nearest_p, 1);
					}
				}
				result = '';
				while (lcs.length) {
					result += lcs.pop();
				}
				console.log("最长公共子序列为：" + result);
				return result;
			}
		</script>
		<div id="footer" class="footer" style="bottom: 0px; width: 100%;position: fixed;z-index: -10;font-family: Consolas;">
			<style type="text/css">
				.footer {
					text-align: center;
				}

				.footer a {
					color: #000000;
					text-decoration: none;
				}
			</style>
			<p><strong>Copyright</strong> © 2021 <strong>邓永盛</strong>. <strong>All rights reserved.</strong></p>
			<p><a href="https://beian.miit.gov.cn/">鄂ICP备2021018056号-1</a></p>
			<p>
				<a href="https://gitee.com/deng-yongsheng"><strong>Git</strong>主页</a>
				<a href="mailto:dys.tj@qq.com?subject=来自gp.dengyongsheng.cn的访客">Email:dys.tj@qq.com</a>
			</p>
			<script type="text/javascript">
				function setPosition() {
					if (window.innerHeight - 70 > document.body.clientHeight) {
						document.getElementById('footer').style.position = 'fixed';
					} else {
						document.getElementById('footer').style.position = 'relative';
					}
				}
				document.body.onresize = setPosition;
				window.onresize = setPosition;
				setPosition();
			</script>
			<script>
				var _hmt = _hmt || [];
				(function() {
					var hm = document.createElement("script");
					hm.src = "https://hm.baidu.com/hm.js?d564375877ebc5c0c21628a5ce920dac";
					var s = document.getElementsByTagName("script")[0];
					s.parentNode.insertBefore(hm, s);
				})();
			</script>
		</div>
	</body>
</html>
